package com.example.algorithm.DHash;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author: dangwen
 * @createDate: 2021/6/15
 * 242. 有效的字母异位词
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 * 示例 1:
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 *
 * 示例 2:
 * 输入: s = "rat", t = "car"
 * 输出: false
 */
public class Anagram {
    /**
     * 该方法处理不了有特殊字符的情况
     */
    public boolean isAnagram1(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        char[] c1 = s.toCharArray();
        char[] c2 = t.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        return Arrays.equals(c1,c2);
    }

    /**
     * 该方法无论是从时间复杂度，空间复杂度，还是特殊字符来讲，都要更加强大。完美解。
     */
    public static boolean isAnagram2(String s, String t){
        if(s.length() != t.length()){
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c,0) + 1);
        }
        for(int i = 0; i < t.length(); i++){
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) - 1);
            if(map.get(c) < 0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s1 = "cat";
        String s2 = "at";
        System.out.println(isAnagram2(s1,s2));;
    }
}
